package org.example.Soution001;

public class FindKthLargestMaxHeap {
    public static void main(String[] args) {
        int[] nums={1,2,3,4,5,6,7,8,9};
        int k=1;
        FindKthLargestMaxHeap obj=new FindKthLargestMaxHeap();
        System.out.println(obj.findKthLargest(nums,k));

    }

    //使用大根堆的方法去处理
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        //建大根堆
        BuildMaxHeap(nums,n);
        //遍历根节点
        for(int i=nums.length-1;i> nums.length-k;i--){
            swap(nums,0,i);
            --n;
            maxHeap(nums,0,n);
        }
        return nums[0];
    }

    public void BuildMaxHeap(int[] nums,int end){
        //从最后一个不为叶子节点的节点开始构建大根堆
        int lastNotLeaf=(nums.length>>1)-1;
        for(int i=lastNotLeaf;i>=0;i--){
            maxHeap(nums,i,end);
        }
    }

    public void maxHeap(int[] nums,int root,int end){
        int left=root*2+1,right=root*2+2,bigest=root;
            if(left<end && nums[left]>nums[bigest]){
                bigest=left;
            }
            if(right<end && nums[right]>nums[bigest]){
                bigest=right;
            }
            if(bigest!=root){
                swap(nums,bigest,root);
                maxHeap(nums,bigest,end);
            }
    }

    public void swap(int[] nums,int i,int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
}
